/*
 * 分数的运算，用于beat
 * 用三元组[int, num, den]表示分数int + num / den
 * 除normalize外，所有函数都要求输入是标准形式，即满足int是整数，num是非负整数，den是正整数，0 ≤ num < den
 * 所有函数都返回标准形式
 * 运算时会“记住”分母，不会约分。例如1/2 + 1/6 = 4/6，2/4 + 1/6 = 8/12，2/4 * 3/6 = 6/24
 * 当分子分母过大时内部运算可能损失精度，函数内不检查。安全范围：
 *     标准化：|int| < 2^48, |num| < 2^48, den < 2^48
 *     绝对值、约分等：|int| < 2^48, den < 2^48
 *     加减法、比较：|int| < 2^48, den < 2^24
 *     乘法：|int| < 2^24, den < 2^24
 *     除法：|int| < 2^24, den < 2^24，且除数通分（不约分）后分子绝对值 < 2^24
 */


exports.gcd = function(x, y) {
	var a = x, b = y, c = y;
	while (c != 0) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
};


// 转成标准形式，要求x[0]、x[1]是整数，x[2]是正整数
exports.normalize = function(x) {
	var t = Math.floor(x[1] / x[2]);
	return [x[0] + t, x[1] - t * x[2], x[2]];
};


// 约分
exports.reduce = function(x) {
	var t = this.gcd(x[1], x[2]);
	return [x[0], x[1] / t, x[2] / t];
};

// 转成浮点数
exports.toFloat = function(x) {
	return x[0] + x[1] / x[2];
};


// 给定分母，把浮点数转换成最近的分数
exports.fromFloat = function(f, den) {
	var i = Math.round(f);
	var num = Math.round((f - i) * den);
	if (num < 0) {
		return [i - 1, num + den, den];
	} else {
		return [i, num, den];
	}
};


// 取反
exports.negate = function(x) {
	if (x[1] == 0) {
		return [-x[0], 0, x[2]];
	} else {
		return [-1 - x[0], x[2] - x[1], x[2]];
	}
};


// 绝对值
exports.abs = function(x) {
	if (x[0] < 0) {
		return this.negate(x);
	} else {
		return x.concat();
	}
};


// 加法
exports.add = function(x, y) {
	if(y[2] == 0) {
		//加整数beat的简单处理
		return [x[0] + y[0], x[1], x[2]];
	}else if (x[2] == y[2]) {
		// 常见的同分母加法特殊处理
		var sn = x[1] + y[1];
		if (sn >= x[2]) {
			return [x[0] + y[0] + 1, sn - x[2], x[2]];
		} else {
			return [x[0] + y[0], sn, x[2]];
		}
	} else {
		var d = this.gcd(x[2], y[2]);
		var yd = y[2] / d;
		var sn = x[1] * yd + y[1] * (x[2] / d);
		var sd = x[2] * yd;
		if (sn >= sd) {
			return [x[0] + y[0] + 1, sn - sd, sd];
		} else {
			return [x[0] + y[0], sn, sd];
		}
	}
};


// 减法
exports.subtract = function(x, y) {
	if (x[2] == y[2]) {
		var sn = x[1] - y[1];
		if (sn < 0) {
			return [x[0] - y[0] - 1, sn + x[2], x[2]];
		} else {
			return [x[0] - y[0], sn, x[2]];
		}
	} else {
		var d = this.gcd(x[2], y[2]);
		var yd = y[2] / d;
		var sn = x[1] * yd - y[1] * (x[2] / d);
		var sd = x[2] * yd;
		if (sn < 0) {
			return [x[0] - y[0] - 1, sn + sd, sd];
		} else {
			return [x[0] - y[0], sn, sd];
		}
	}
};


// 乘法
exports.multiply = function(x, y) {
	var s11 = this.normalize([0, x[0] * y[1], y[2]]);
	var s12 = this.normalize([0, y[0] * x[1], x[2]]);
	return this.normalize([x[0] * y[0] + (s11[0] + s12[0]), s11[1] * x[2] + s12[1] * y[2] + x[1] * y[1], x[2] * y[2]]);
};


// 除法，内部不检查除0
exports.divide = function(x, y) {
	var yn = y[0] * y[2] + y[1];
	if (yn < 0) {
		return this.multiply(x, [0, -y[2], -yn]);
	} else {
		return this.multiply(x, [0, y[2], yn]);
	}
};



// 与0比较，返回-1、0或1（不是三元组）
exports.sign = function(x) {
	if (x[0] < 0) {
		return -1;
	} else if (x[0] > 0 || x[1] > 0) {
		return 1;
	} else {
		return 0;
	}
};


/**
 *  比较，返回-1、0或1（不是三元组）
 *  x < y   -1
 *  x == y   0
 *  x > y   1
 * @param x
 * @param y
 * @returns {number}
 */
exports.compare = function(x, y) {
	if (x[0] < y[0]) {
		return -1;
	} else if (x[0] > y[0]) {
		return 1;
	} else {
		var dn = x[1] * y[2] - y[1] * x[2];
		if (dn == 0) {
			return 0;
		} else if (dn < 0) {
			return -1;
		} else {
			return 1;
		}
	}
};
